# 合并两个数组，要求a[n], b[m], O(m+n)
def merge_sorted_list(sorted_a, sorted_b):
    # 合并两个有序序列，返回一个新的有序序列
    length_a, length_b = len(sorted_a), len(sorted_b)
    a = b = 0
    new_sorted_seq = []

    while a < length_a and b < length_b:
        if sorted_a[a] < sorted_b[b]:
            new_sorted_seq.append(sorted_a[a])
            a += 1
        else:
            new_sorted_seq.append(sorted_b[b])
            b += 1
    # 不满足上述两种情况时，将多余的一个最大元素放到有序数组里
    while a < length_a:
        new_sorted_seq.append(sorted_a[a])
        a += 1
    while b < length_b:
        new_sorted_seq.append(sorted_b[b])
        b += 1

    return new_sorted_seq


# 归并排序
# 上面实现了合并两个有序数组，实现归并排序就非常方便了
def merge_sort(seq):
    # 递归出口
    if len(seq) <= 1:
        return seq
    else:
        mid = int(len(seq) / 2)
        left_half = merge_sort(seq[:mid])
        right_half = merge_sort(seq[mid:])

        new_seq = merge_sorted_list(left_half, right_half)

        return new_seq


l1 = [1, 3, 5, 7, 9, 10]
l2 = [2, 4, 6, 8, 11]
result = merge_sorted_list(l1, l2)
print(result)

print("==================================================")


def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    # 二分分解
    num = len(alist) // 2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    # 合并
    return merge(left, right)


def merge(left, right):
    """合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组"""
    # left与right的下标指针
    l, r = 0, 0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result


alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
sorted_alist = merge_sort(alist)
print(sorted_alist)


# 时间复杂度
#
# 最优时间复杂度：O(nlogn)
# 最坏时间复杂度：O(nlogn)
# 稳定性：稳定
